#!/usr/env python
#-*-coding: utf-8 -*-

#INSERTION-SORT(A)
# for j = 2 to A.çength
#  key = A[j]
#insert A[j] into the sorted seq
# i = j - 1
# while(i > 0 and A[j] > key)
#  A[j+1] = A[j]
#  i = i-1
# A[i+1] = key
#

class InsertionSort:
    
    def __init__(self):
        """contrutor da classe
        """
        pass
    pass
    
    #
    # InsertionSort algoritm
    # - arrayA, the list to be sorted
    def insertion_Sort(self, arrayA):
        """ insertionSort algoritm to  sort a list
        of unsorted objects.
        arrayA - list of object to sort
        """
        for k in xrange(1, len(arrayA)):
            key = arrayA[k]
            i = k - 1
            while(i >= 0 and arrayA[i] > key):
                arrayA[i +1] = arrayA[i]
                i -= 1
            pass
            arrayA[i +1] = key
        pass
    pass
pass
